#include <stdio.h>
#include <ctime>
#include <getopt.h>
#include <cstring>

clock_t start;
clock_t finish;
#define MAX_L 9
#define UNKNOW_FLAG 0
#define KNOW_FLAG 2
char flags[MAX_L][MAX_L]={0};
char data[MAX_L][MAX_L]={0};
char *input_file;
typedef void sFn(char p[][MAX_L]);

extern void getChessFromFile(char *filename,sFn func);

void showData(char p[][MAX_L]){
	int len = MAX_L;
	for(int i = 0;i< len;i++){
	  for(int j=0;j<len;j++)
		  printf("%2d",p[i][j]);
	  printf("\n");	
	}
   printf("---------------------------------------------------\n");	
}
void showChess(char p[][3]){
 int len =3;	
	for(int i = 0;i< len;i++){
	  for(int j=0;j<len;j++)
		  printf("%2d",p[i][j]);
	  printf("\n");	
	}
   printf("---------------------------------------------------\n");	
}

void setFlags(){
	  for(int i =0;i<MAX_L;i++)
	  for(int j = 0;j<MAX_L;j++){
		  if(data[i][j] >0 ){
			  flags[i][j]=1;
		  }else{
			  flags[i][j]=UNKNOW_FLAG;
		  }
	  }
}
void getData(){
  data[0][0] = 8;
  data[1][1] = 7;
  data[1][4] = 9;
  data[1][6] = 2;
  data[2][2] = 3;
  data[2][3] = 6;
  data[3][1] = 5;
  data[3][5] = 7;
  data[4][4] = 4;
  data[4][5] = 5;
  data[4][6] = 7;
  data[5][3] = 1;
  data[5][7] = 3;
  data[6][2] = 1;
  data[6][7] = 6;
  data[6][8] = 8;
  data[7][2] = 8;
  data[7][3] = 5;
  data[7][7] = 1;
  data[8][1] = 9;
  data[8][6] = 4;
  data[8][8] = 0;

}

int check(){
     
  for(int i =0;i<MAX_L;i++)
	  for(int j = 0;j<MAX_L;j++){
		  if(flags[i][j] == UNKNOW_FLAG)
			  return 1;
	  }
	return 0;
}
int findNextPos(int * row,int * col){
  int j = *col;	
  for(int i =*row;i<MAX_L;i++){
	  for(;j<MAX_L;j++){
		  if(flags[i][j] == UNKNOW_FLAG){
			  *row = i;
			  *col = j;
			  return 1;
		  }
	  }
	  j = 0;
  }


	return 0;

}

int checkrow(int num,int row){
	for(int i=0;i< MAX_L;i++){
		if(data[row][i]== num)
			return 0;
	}

	return 1;
}
int checkcol(int num,int col){
	for(int i =0;i <MAX_L;i++){
		if(data [i][col]== num){
                  return 0;
		}
	}
	return 1;
}

void getchess(char p[][3],int row, int col){
int	a = (row) /3;
int     b = (col) /3;
int s_row = a*3;
int s_col = b*3; 
for(int i=s_row;i<3+s_row;i++)
	for(int j=s_col;j<3+s_col;j++){
		p[i-s_row][j-s_col]=data[i][j];
	}
 
}

int checkrowcol(int num,int row,int col){
	char chess[3][3]={0};
	getchess(chess,row,col);
	//showChess(chess);
	for(int i=0;i<3;i++){
		for(int j =0;j<3;j++)
			if(chess[i][j]==num)
				return 0;
	}
	return 1;
}
int findTestNum(int  row, int col){
	int current = data[row][col];
	for(int i= current+1;i<=MAX_L;i++){
		if(checkrow(i,row) && checkcol(i,col) && checkrowcol(i,row,col)){
	//	if(checkrow(i,row) && checkcol(i,col) ){
			return i;
		}	
	}
	return 0;
}
void setTestNum(int numb,int row, int col,int ok){
	
	if(ok){
		data[row][col]= numb;
		flags[row][col] = KNOW_FLAG;
	}else{
		data[row][col]=0;
		flags[row][col] = UNKNOW_FLAG;
	}

}	

int findPrePos(int * row,int *col)
{
	int j = *col;
	for(int i = *row;i>=0;i--){
		for(;j>=0;j--){
		  if(flags[i][j]== KNOW_FLAG ){
			  *row = i;
		  	  *col = j;
		 
			  return 1;
		  }
		}
		j = MAX_L;
	}
	return 0;
}

void pars_opts(int argc,char * argv[]){
	
		int		c;
		while ((c = getopt(argc, argv, "i:h")) != EOF) {
			switch (c) {
			case 'i':
				input_file = optarg;
				break;
			case 'h':
				printf("sdr -i inputfile\n");
                 break;	
			default:
				printf("sdr -i inputfile\n");
				break;
			}
		}

}
void sovle(char p[][MAX_L]){
	
	int row =0;
	int col =0;
	int res = 0;
	int count = 0;
	start = clock();
	
	getData();
	if(p){
		memcpy(data,p,sizeof(data));
	}
	setFlags();
	showData(data);
//	showData(flags);
	res = findNextPos(&row,&col);
	//printf("row = %d ,col %d \n",row,col);
	while(check()){
		count ++;;
		//showData(data);
		//showData(flags);
		res = findTestNum(row,col);
		if(res){
			setTestNum(res,row,col,1);
			res = findNextPos(&row,&col);
		//	printf("row = %d ,col %d \n",row,col);
			if(!res)
				break;
		}else{
			setTestNum(res,row,col,0);
		   	res = findPrePos(&row,&col);
			if(!res){
				printf("fial to find result\n");
				break;
			}
		}
	
	}
//	showData(flags);
	showData(data);	
	finish= clock();
	printf("total count = %d  time = %f \n\n",count,(double)(finish-start)/CLOCKS_PER_SEC);

}
int main(int argc,char ** argv)
{
	
	pars_opts(argc,argv);
	if(input_file){
	  memset(data,0,sizeof(data));
	  getChessFromFile(input_file,sovle);
	}else{
		sovle(NULL);
	}

	return 0;
}
